Regular Expressions

We can compose additional regular expressions by applying the following rules a finite number of times:

• If r₁ is a regular expression, then so is (r₁).
• If r₁ is a regular expression, then so is r₁*.
• If If r₁ and r₂ are regular expressions, then so is r₁r₂.
• If If r₁ and r₂ are regular expressions, then so is r₁+r₂.

• Parentheses are just used for grouping.

• The postfix star indicates zero or more repetitions of the preceding regular expression. Thus, if x , then the regular expression x* denotes the language {, x, xx, xxx, ...}.

• Juxtaposition of r₁ and r₂ indicates any string described by r₁ immediately followed by any string described by r₂. For example, if x, y , then the regular expression xy describes the language {xy}.

• The plus sign, read as "or," denotes the language containing strings described by either of the component regular expressions. For example, if x, y , then the regular expression x+y describes the language {x, y}.